package com.atguigu.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
import java.util.Random;

/**
 * @author shkstart
 * @create 2021-08-20 14:57
 */
//快速排序法：用时不到一秒
public class QuickSort {
    public static void main(String[] args) {
////                int arr[]={101,34,119,1};
////        quickSort(arr,0,arr.length-1);
////        System.out.println(Arrays.toString(arr));
//        //时间复杂度O(n^2)
//        //该台电脑使用时间：3秒左右
////        int[] arr ={3,9,-1,10,-2};
//
//        int[] arr = new int[80000];
//        for (int i=0;i<80000;i++){
//            arr[i]=(int)(Math.random()*800000);
//        }
//        Date date1 = new Date();
//        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
//        String format = simpleDateFormat.format(date1);
//        System.out.println("排序前的时间="+format);
//
//       quickSort(arr,0,arr.length-1);
////        System.out.println(Arrays.toString(arr));
//        Date date2 = new Date();
////        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
//        String format2 = simpleDateFormat.format(date2);
//        System.out.println("排序后的时间="+format2);
        //给出无序数组
        int arr[] = {72,6,57,88,60,42,83,73,48,85};

        //输出无序数组
        System.out.println(Arrays.toString(arr));
        //快速排序
        quickSort(arr);
        //partition(arr,0,arr.length-1);
        //输出有序数组
        System.out.println(Arrays.toString(arr));

    }
//    public static void quickSort(int[] arr,int left,int right){
//        int l=left;
//        int r=right;
//        int temp=0;
//        int pivot=arr[(left+right)/2];
//        while (l<r){
//            //一次寻找
//            //向左寻找，找到一个就退出
//            while (arr[l]<pivot){
//                l++;
//            }
//            //向右寻找，找到一个就退出
//            while (arr[r]>pivot){
//                r --;
//            }
//            //如果一直寻找，直到两种相遇，那就说明不用再寻找了，退出循环
//            if (l>=r){
//                break;
//            }
//            //如果找到了，那就交换
//            temp=arr[l];
//            arr[l]=arr[r];
//            arr[r]=temp;
//            //如果发现交换完成之后的数字==pivot，那就说明之前的arr[r]==pivot,那就跳过此数，下一个循环
//            if (arr[l]==pivot){
//                r--;
//            }
//            //如果发现交换完成之后的数字==pivot，那就说明之前的arr[l]==pivot,那就跳过此数，下一个循环
//            if (arr[r]==pivot){
//                l++;
//            }
//        }
//        //一个找得比较快，那就必须越过
//        if (l==r){
//            l++;
//            r--;
//        }
//        if (left<r){
//            quickSort(arr,left,r);
//        }
//        if (right>l){
//            quickSort(arr,l,right);
//        }
//    }
    //分区，确定轴值
public static int parttion(int[] arr,int left,int right) {
    int i = left;
    int j = right;
    int x = arr[left];
    while (i < j) {
        //右指针向右移动
        while (arr[j] >= x && i < j) {
            j--;
        }
        if (i < j) {
            arr[i] = arr[j];
        }
        //左指针向右移动
        while (arr[i] < x && i < j) {
            i++;
        }
        if (i < j) {
            arr[j] = arr[i];
        }


    }
    arr[i] = x;
    return i;
}
    public static void quickSort(int[] arr,int left,int right){
      if (left<right){
          int index = parttion(arr, left, right);
          quickSort(arr,left,index-1);
          quickSort(arr,index+1,right);
      }
    }
    public static void quickSort(int[] arr) {

        int left=0;
        int right=arr.length-1;
        quickSort(arr,left,right);
    }

}

